package mid.class4;

import common.ArrayUtils;

public class TestDemo {

    public static void main(String[] args) {
        UnionFind unionFind = new UnionFind(10);
        unionFind.union(0, 1);
        unionFind.union(2, 3);
        ArrayUtils.printArr(unionFind.father);
        ArrayUtils.printArr(unionFind.size);
        unionFind.union(0, 2);
        ArrayUtils.printArr(unionFind.father);
        ArrayUtils.printArr(unionFind.size);
        int i = unionFind.find(0);
        System.out.println(i);
        ArrayUtils.printArr(unionFind.father);
        ArrayUtils.printArr(unionFind.size);
    }

    private static class UnionFind {

        public int[] father;
        public int[] size;

        public UnionFind(int m) {
            this.father = new int[m];
            this.size = new int[m];
            for (int i = 0; i < m; i++) {
                father[i] = i;
                size[i] = 1;
            }
        }

        public int find(int i) {
            if (i != father[i]) {
                father[i] = find(father[i]);
            }
            return father[i];
        }

        public boolean isSame(int x, int y) {
            return find(x) == find(y);
        }

        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                size[fy] += size[fx];
                father[fx] = fy;
            }
        }
    }
}
